package woa.stack;

import java.util.Stack;

/**
 * 字符串解码
 * 给定一个经过编码的字符串，返回它解码后的字符串。
 * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
 * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
 * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
 *
 * 输入：s = "3[a]2[bc]"
 * 输出："aaabcbc"
 *
 * 输入：s = "3[a2[c]]"
 * 输出："accaccacc"
 *
 * @author wangpeng
 * @date 2021/12/1
 */
public class DecodeStringProblem {

    public static String decodeString(String s) {
        String rs = "";
        Stack<String> stack = new Stack<String>();
        char[] chars = s.toCharArray();
        String numStr = "";
        for (char c : chars) {
            if (Character.isDigit(c)) {
                numStr += c;
            } else {
                if (!"".equals(numStr)) {
                    stack.push(numStr);
                    numStr = "";
                }
                if (c == ']') {
                    String temp = "";
                    while (!stack.isEmpty()) {
                        if (stack.peek().equals("[")) {
                            stack.pop();
                            break;
                        }
                        temp = stack.pop() + temp;
                    }
                    int num = Integer.valueOf(stack.pop());
                    stack.push(decodeByNum(num, temp));
                } else {
                    stack.push(String.valueOf(c));
                }
            }
        }

        while (!stack.isEmpty()) {
            rs = stack.pop() + rs;
        }
        return rs;
    }

    public static String decodeByNum(int num, String s) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < num; i++) {
            builder.append(s);
        }

        return builder.toString();
    }

    public static void main(String[] args) {
        System.out.println(decodeString("aa3[2[c]a2[b]]ef"));
    }
}
